package tianhao.luo.binarysorttree;

/**
 * 二叉排序树
 * @author: tianhao.luo@hand-china.com 2021/6/27  上午9:26
 */
public class BinarySortTree {
    /**
     * 根节点
     */
    private Node root;


    public void add(Node node){
        // 为空时该结点就是root
        if (root == null){
            root = node;
        }else {
            root.add(node);
        }
    }

    public void infixOrder(){
        if (root !=null){
            root.infixOrder();
        }else {
            System.out.println("二叉排序树为空");
        }
    }

    // 查找当前结点
    public Node search(int value){
        if (root == null){
            return null;
        }else {
            return root.searchNode(value);
        }
    }


    // 查找父节点
    public Node searchParent(int value){
        if (root == null){
            return null;
        }else {
            return root.searchParent(value);
        }
    }

    public void delNode(int value){
        if (root == null){
            return;
        }else {
            // 1. 找到要删除的结点
            Node targetNode = search(value);
            // 2. 没有找到删除的结点
            if (targetNode == null){
                return;
            }
            // 3. 如果发现这颗二叉排序树只有一个结点
            if(root.left == null && root.right == null){
                root =null;
                return;
            }

            // 4. 去找到targetNode的父节点
            Node parentNode = searchParent(value);

            // 如果删除的结点是叶子结点
            if (targetNode.left == null && targetNode.right == null){
                // 判断targetNode是父节点的左子节点还是右子节点
                if (parentNode.left !=null && parentNode.left.value == value){
                    // 是左子节点
                    parentNode.left = null;
                }else if (parentNode.right !=null && parentNode.right.value ==value){
                    parentNode.right =null;
                }
            }
            // 删除的是有两颗子树的结点
            else if (targetNode.left !=null && targetNode.right !=null){
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
                /**
                 * 使用左子树查找最大结点
                 * int maxVal = delLeftTreeMax(targetNode.left);
                 * targetNode.value = maxVal;
                 */
            }
            // 删除只有一个子树的结点
            else {
                // 如果要删除的结点有左子节点
                if (targetNode.left !=null){
                    if (parentNode != null){
                        // 当前结点是父节点的左结点
                        if (parentNode.left.value == value){
                            parentNode.left = targetNode.left;
                        }else {
                            // target是parent的右子节点
                            parentNode.right = targetNode.left;
                        }
                    }else {
                        // 删除的恰好是根节点了
                        root = targetNode;
                    }
                }else {
                    if (parentNode !=null){
                        // 删除的结点只有右子节点

                        // 删除的结点是父节点的左结点
                        if (parentNode.left.value == value){
                            parentNode.left =targetNode.right;
                        }else {
                            parentNode.right = targetNode.right;
                        }
                    }else {
                        root = targetNode;
                    }
                }

                // 判断targetNode是父节点的左子节点还是右子节点
                if (parentNode.left !=null && parentNode.left.value == value){
                    // 是左子节点
                    parentNode.left = null;
                }else if (parentNode.right !=null && parentNode.right.value ==value){
                    parentNode.right =null;
                }

            }
        }
    }


    /**
     * 1.找到右子树最小的结点
     * 2.删除该结点
     * @param node 传入的结点(当做二叉排序树的根节点)
     * @return 返回以node 为根节点的二叉排序的最小节点的值
     */
    public int delRightTreeMin(Node node){
        Node target = node;
        // 循环的查找左结点,就会找到最小值
        while (target.left !=null){
            target = target.left;
        }
        // target指向了最小结点
        delNode(target.value);
        return target.value;
    }


    /**
     * 1.找到左子树最大的结点
     * 2.删除该结点
     * @param node 传入的结点(当做二叉排序树的根节点)
     * @return 返回以node 为根节点的二叉排序的最小节点的值
     */
    public int delLeftTreeMax(Node node){
        Node target = node;
        // 循环的查找右结点,就会找到最大值
        while (target.right !=null){
            target = target.right;
        }
        // target指向了最大结点
        delNode(target.value);
        return target.value;
    }
}
